In packet-switched networks, packets in the form of blocks of data are transmitted from a source--such as a user terminal, computer, application program within a computer, or other data handling or data communication device--to a destination, which may be simply another data handling or data communication device of the same character. The devices themselves typically are referred to as users, in the context of the network. Packet switching arose, in part, to fulfill the need for low cost data communications in networks developed to allow access to host computers. Special purpose computers designated as communication processors have been developed to offload the communication handling tasks which were formerly required of the host. The communication processor is adapted to interface with the host and to route packets along the network; consequently, such a processor is often simply called a packet switch.
Packet-switched data transmission may be accomplished via predetermined end-to-end paths through the network, in which user packets associated with a great number of users share link and switch facilities as the packets travel over the network. Accordingly, the packets require storage at nodes between transmission links of the network until they may be forwarded along the respective outgoing link for the overall path. This type of data transmission is generally referred to as virtual circuit or connection-oriented transmission.
Another mode of packet-switched data transmission requires no initial connection for a data path through the network, and, hence, is termed connectionless transmission. In this mode, individual datagrams carrying a destination address are routed through the network from source to destination via intermediate nodes, and do not necessarily arrive in the order in which they were transmitted.
By way of example, in the widely-used Telenet public packet-switched network the routing of data is accomplished using a two-level hierarchy. The hierarchy comprises a long distance-spanning backbone network with a multiplicity of hubs or nodes, each of which utilizes a cluster of backbone switches; and smaller geographic area networks with backbone trunks, access lines and clustered lower level switches connected to each hub. Packet-switched data transmission through the network is accomplished by means of the virtual circuit connection-oriented mode using CCITT (International Telegraph and Telephone Consultative Committee of the International Telecommunications Union) X.75 protocol, which is a compatible enhancement of X.25 protocol.
X.25 is an interface organized as a three-layered architecture for connecting data terminals, computers, and other user systems or devices, generally referred to as data terminal equipment (DTE), to a packet-switched network through data circuit terminating equipment (DCE) utilized to control the DTE's access to the network. The three layers of the X.25 interface architecture are the physical level, the frame level and the packet level. Although data communication between DCEs of the network is routinely handled by the network operator typically using techniques other than X.25, communication between the individual user system and the respective DCE with which it interfaces to the network is governed by the X.25 or similar protocol. In essence, X.25 establishes procedures for congestion control among users, as well as call setup (or connect) and call clearing (or disconnect) for individual users, handling of errors, and various other packet transmission services within the DTE-DCE interface.
The X.75 protocol used in the Telenet network features the same call set up and packet handling procedures as X.25, with various enhancements including higher bit rates (56 kbps) at the physical level, extended sequence numbering at the frame level, and additional utility field for call setup packets at the packet level. A special multilink protocol governs handling of established virtual circuits with respect to load sharing and recovery from link failures. In the event of failure of a trunk group or transmit hub, a reconnect procedure is required to reestablish a transmission path. Each call is initiated by a user-transmitted call-request packet. It is noteworthy that the Telenet public packet-switched network employs the X.75 protocol for routing the call-request packet through the entire backbone network via an appropriate route, rather than merely as an interface between DTEs and DCEs or between networks. Acknowledging acceptance of calls, call clearance, and certain other functions are provided using other X.25 control packets.
Prospective routing paths in the Telenet network are initially determined by a network control center, which then transmits these predetermined paths to the backbone switches as routing tables consisting of primary and secondary choices of available links from each hub. The secondary choices are viable only in the event of primary link failures, and the specific secondary link selection is a local decision at the respective hub based principally on current or recent traffic congestion patterns. The unavailability of an outgoing link from a hub at the time of the call setup effects a clearing back of the predetermined virtual circuit for the sought call to the preceding hub. An alternative link is then selected by that hub, or, if none is available there, the virtual circuit is again cleared back to the next preceding hub, and so forth, until an available path is uncovered from the routing tables. Messages concerning link and/or hub failures are communicated immediately to the network control center, and that information is dispatched to the rest of the network by the center.
The switches used in the Telenet public network and various of its private networks are members of the multiprocessor TP4000 (sometimes referred to in abbreviated fashion as TP4) packet switch family. The basic switch includes line processing units (LPUs) for overseeing the lines to the DTEs, whether terminals, hosts or otherwise, and the network trunks (at the X.25 frame level), and a central processing unit (CPU) for routing at the packet level. The CPU, using a stored table of trunk-to-trunk active virtual circuits, maps the identity of the access-seeking LPU, its line number and the associated logical channel relative to the outgoing counterparts, for an identified virtual circuit at the respective hub.
The present generation (prior art) TP4000 packet switch (or communication processor) has been designated as the TP4000/II. Referring now to FIG. 1, the basic configuration of the TP4000/II includes a main memory unit 10, an arbitrator unit (ARB) 12, a CPU 15, and a plurality of LPUs 17-1 through 17-n coupled and vying for access to either of a pair of demand assign buses (DABs) 20A and 20B. Access for packet transmissions is controlled by ARB 12. Connected to each LPU 17 is an associated interface unit 22 to which a respective input port, for example modem 25, is connected. The interface unit converts to external signal levels (RS232, etc.), on data entering the interface from each modem. From that point onward through the switch, everything is in the converted level until a level conversion is performed back to the original format by an interface 22 associated with a respective LPU 17-x upon subsequent re-transmission of the data from the switch.
A typical LPU I7 of the type used in the TP4000/II packet switch of FIG. i is shown in block diagrammatic form in FIG. 2. The LPU has serial interface ports or serial interface controllers constituting serial input/output ports (SIOs) 27 which are connected to the interface 22. Data from the modem is subjected to level conversion by the interface card 22 prior to entry into the LPU. It should be mentioned that references from time to time herein to a card or cards is merely in recognition that the particular unit being described is embodied in a printed circuit card and the various electronic components mounted and interconnected thereon. The level-converted data then proceeds into an applicable channel of the LPU. Each LPU may handle eight ports, for example, and because one-to-one mapping is used, the associated interface would also handle eight ports. The SIO units convert the incoming data from serial to parallel format, and handle some of the very low level protocols, such as checking for errors, and the like.
After the data conversion from serial to 8-bit parallel format, a direct memory access (DMA) controller 30 of the LPU performs a move function by which blocks of data are moved from one particular location to another particular location. Accordingly, the 8-bit parallel data is read out by the DMA controller 30 and the blocks of data are thereby transferred out on one of the two DAB buses 20 (A or B) and into a particular location in the main memory 10 (FIG. 1). The DMA controller controls all eight ports in a perfunctory manner, being programmed by a 6502 processor 32 to store the information for each channel in a particular location in the main memory by movement in blocks of data. The 6502 processor utilizes local random access memory (RAM) 84 and read-only memory (ROM) 35 in carrying out its functions. A redundant DAB interface 87 is provided to the pair of DAB buses 20 A and B to accommodate movement of the blocks of data onto either bus in the event of a failure on the other bus.
Referring again to FIG the arbitrator unit 12, main memory unit 10 and backplane bus 20 of the TP4000/II packet switch are an integral unit. The arbitrator controls access to the bus, but since there is essentiallY only one bus (in view of the redundancy feature) to the main memory, the process may be viewed as an arbitration for access to main memory rather than an arbitration for access to the bus. The integral unit constitutes a single resource with redundant memory, redundant arbitrator and redundant bus (that is, backup for each), in which switching to the backup unit is performed in the event of a failure of the arbitrator, the main memory or the bus.
Once data is transferred into the main memory 10, CPU 15 monitors that data and the intercard (i.e., LPUs and other units of the switch) communication areas, to determine where the data should now be transferred. The CPU then notifies an appropriate LPU that particular data in the main memory is to be transferred to that LPU. Accordingly, the path of data is via a modem through an LPU, with arbitration onto the bus and into main memory. Then a processing decision is made by the CPU as to the intra-switch destination for the data, and the CPU thereupon notifies the other card (the LPU), whereupon the data is transferred out of main memory through the selected LPU, its associated interface, and out through that modem or port. This is the manner in which the TP4000/II switch performs its packet switching. The packetizing (i.e., packet assembly) is accomplished in the LPU. Asynchronous data is received, packets are formed, and the packets are subsequently switched throughout the network until, at the other end, the packet is disassembled and transferred as asynchronous data again.
The TP4000/II arbitration protocol on the DAB bus treats CPUs separately from LPUs. A block diagram useful for describing the protocol is shown in FIG. 3. The LPUs 40-1, 40-2, 40-n compete for access to the bus, in order to have their respective data packets (if any) read into the main memory. The competition is arbitrated by ARB unit 42 in a daisy chain approach by which the ARB initially passes a token to the LPU 40-1. If that LPU is ready to use the bus, it will hold the token and the bus, and on completion of its use will pass the token to the next LPU in the chain. If at that point LPU 40-2 has no need for access to the bus, it will simply pass the token to the next LPU. Finally, the last LPU in the chain, 40-n, passes the token back to the ARB 42. The scheme is such that the holder of the token holds possession of the bus. A separate token is employed for the CPUs 45-1 and 45-2, and here again a daisy chain approach is employed for the arbitration. If the CPUs are not using their bus time, the LPUs may use it.
With this protocol, there may be passage of considerable time for the token to travel between units before the unit presently desiring to use the bus is encountered. That is, if LPU 40-1, for example, initially receives the token and has no present need to use the bus, the token is passed from LPU to LPU, When perhaps only LPU 40-15 is in need of access. Viewing the bus protocol of FIG. 3 in terms of clock cycles, a CPU or an LPU will remain idle and waiting until the token is passed to it--indeed, the unit may sit and wait until the token passes through a considerable number of LPUs until it finally gets the token--despite the fact that it may be the only card that is seeking to transfer data and, therefore, that requires the bus.
Hence, time, and as a result, valuable bandwidth may be wasted as the token is passed from card to card until a need to use the bus is found. Moreover, as previously noted, at least some of the units within the packet switch, such as the LPUs, are individually configured on respective printed circuit cards. These cards are inserted into designated slots in cages within a console. The bus protocol requires that a ribbon cable be run between cages, with an attendant further slowing of the bus.
Although an LPU may gain control of the bus, it is essential to the retention of control that a response (acknowledgment) must be delivered to indicate that the message was received. The response is pipelined at fixed intervals; that is to say, the LPU monitors for the acknowledgment at a particular clock cycle by counting clock cycles, and if the acknowledgment is not received at the point when it should have returned, this is an indication that a problem has arisen.
Many other prior art packet switches (i.e., besides the TP4000/II) use the same or similar bus protocols. For example, one bus type employs multiple bus request chains, with separate predetermined priorities, each chain employing an arbitration scheme corresponding to that described above. Another form of prior art packet switch uses a slightly different scheme, in that whenever a unit has need for access to the bus, that unit must transmit a particular pattern onto the arbitration bus. Hence, many units may be driving the arbitration bus at the same time. Periodically, the driving units read the patterns and make a decision as to whether to remain a requester or to abandon the request, based on the apparent priorities of other requesters, until a winner is declared. The process may take several clock cycles before the determination of a winner is made.
Each of these other prior art arbitration schemes suffers disadvantages corresponding to those of the aforementioned TP4000/II, namely, that time and bandwidth are wasted as a consequence of the nature of the selection process for an appropriate bus user.
It is a principal object of the present invention to provide an improved packet switch.
A more specific object of the invention is to provide a packet switch, or communication processor, utilizing an improved arbitration scheme that allows any data processor (e.g, packet assembler/disassembler (PAD), CPU, and so forth) to request the bus immediately upon need for access and to have that need assessed within a brief time interval such a single clock cycle.
A further object of the present invention is to provide an improved packet switch in which bus grants are issued within a relatively short time after the respective bus requests are made.
Still another object of the present invention is to provide a packet switch with improved bandwidth utilization.
A further object of the present invention is to provide a packet switch capable of handling a substantially larger number of ports than has heretofore been permissible with prior art packet switches.
The task of achieving a new and improved packet switch requires performance improvements worthy of the cost and time necessary for the effort, together with economic reductions in the cost of manufacture and upkeep, and in the consumption of power; while simultaneously retaining at least some of the significant and desirable aspects and features of the prior art switch on which the improved packet switch is based. In the specific instance of improvement of the multi-processor-based TP4000 packet switch class from the present generation /II to the next generation /III level, it was deemed essential to maintain very nearly the same software architecture, with the attendant necessity that hardware architecture at the upper levels would retain a degree of similarity. Furthermore, it was important that the hardware improvements to be implemented that would allow the software to be run faster and more efficiently. Retention of a substantial part of the existing software was deemed desirable in view of a well-recognized rule against simultaneously changing hardware and software, and by an existing substantial investment in the software employed for the Telenet common carrier network and that used for related private networks.